{
const height = "350px";
const container = d3.create("div").style("position", "relative");
let svg = container
.append("svg")
.attr("class", "canvas")
.style("width", "90%")
.style("height", height);
drawBalls(svg);
svg.on("click", (e) => {
const coord = d3.pointer(e);
isA ? A.push(coord) : B.push(coord);
drawBalls(svg);
});
return container.node();
}Lowering BoundingThe Gromov–Hausdorff Distance on Graphs
Henry Adams, Nicolò Zava, Žiga Virk, Fedor Manin
Sushovan Majhi
George Washington University, Washington D.C.
George Washington University, Washington D.C.
Today’s Agenda
- Hausdorff Distance
- Gromov–Hausdorff Distance
The Hausdorff Distance
Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their Hausdorff distance is \[ \vec{d}_H(X,Y)=\max_{x\in X}\min_{y\in Y}\|x-y\|. \]
Definition 2 (Hausdorff Distance) \[ d_H(X,Y)=\max\bigg\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\bigg\}. \]
viewof scaleA = Inputs.range([0, 300], {
step: 1,
value: 0,
label: tex`\vec{d}_H(X,Y)`
});
viewof scaleB = Inputs.range([0, 300], {
step: 1,
value: 0,
label: tex`\vec{d}_H(Y,X)`
});
viewof isA = Inputs.toggle({ label: tex`X\text{ or }Y`, value: true });
viewof btn = Inputs.button("clear", {
value: null,
reduce: () => {
A.length = 0;
B.length = 0;
viewof scaleA.value = 0;
viewof scaleB.value = 0;
viewof scaleA.dispatchEvent(new CustomEvent("input"));
viewof scaleB.dispatchEvent(new CustomEvent("input"));
}
});A = [];
B = [];
drawBalls = function (svg) {
svg
.selectAll(".A-ball")
.data(A)
.join("circle")
.attr("class", "A-ball")
.attr("cx", (d) => d[0])
.attr("cy", (d) => d[1])
.attr("r", scaleA)
.attr("fill", "green")
.attr("stroke", "none")
.attr("opacity", "0.4");
svg
.selectAll(".B-ball")
.data(B)
.join("circle")
.attr("class", "B-ball")
.attr("cx", (d) => d[0])
.attr("cy", (d) => d[1])
.attr("r", scaleB)
.attr("fill", "red")
.attr("stroke", "none")
.attr("opacity", "0.4");
svg
.selectAll(".A-vertex")
.data(A)
.join("circle")
.attr("class", "A-vertex")
.attr("cx", (d) => d[0])
.attr("cy", (d) => d[1])
.attr("r", "5px")
.attr("fill", "green")
.on("mouseover", function () {
d3.select(this).attr("fill", "orange").attr("r", "10px");
})
.on("mouseout", function () {
d3.select(this).attr("fill", "green").attr("r", "5px");
});
svg
.selectAll(".B-vertex")
.data(B)
.join("circle")
.attr("class", "B-vertex")
.attr("cx", (d) => d[0])
.attr("cy", (d) => d[1])
.attr("r", "5px")
.attr("fill", "red")
.on("mouseover", function () {
d3.select(this).attr("fill", "orange").attr("r", "10px");
})
.on("mouseout", function () {
d3.select(this).attr("fill", "red").attr("r", "5px");
});
return svg;
}
import { slider } from "@jashkenas/inputs"Why Only Euclidean Subsets?
Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(A, B\subset\) compact subsets. \[ \vec{d}^Z_H(A,B)=\max_{a\in A}\min_{b\in B}d(a, b). \]
\[ d^Z_H(A,B)=\max\bigg\{\vec{d}^Z_H(A,B),\vec{d}^Z_H(B,A)\bigg\}. \]
The Gromov–Hausdorff Distance
- What if the subsets \(X,Y\) have no common embeddding?
Definition 4 (The Gromov–Hausdorff Distance) The Gromov–Hausdorff distance is defined by \[ d_{GH}(X,Y)=\inf d^Z(f(X),g(Y)), \] over all isometries \(f,g\) and common embeddeding space \((Z,d)\).
- \(d_{GH}(A,B)=\) if and only if \(A\), \(B\) are isometric.
- If finite \(|X|=|Y|=n\)
- Computationally feasible (distortion definition)
- Exponential
Hausdorff vs Gromov–Hausdorff
- \((Z,d)\) is a metric space
- \(X\) is a subset
- \((X,d)\) is also a metric space
Non-Trivial Lower Bounds
\(\frac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \frac{1}{2}\max\{diam(X), diam(Y)\}\).
Bad News
For any \(\varepsilon>0\), there exists a compact metric space \(Z\) and a subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < \varepsilon \cdot d_{H}(X,Z).\)
Closed Riemannian Manifolds
Example using Non-Dense subsets of Circle
Our goal is to find lower bounds in terms of the Hausdorff distance.
The natural intuition is when a sample becomes dense enough, it starts to capture the geometry of the space.
Need pictures here.
The Curious Case of the Circle
Theorem 1 (2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{6}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).
- Is \(\frac{\pi}{6}\) optimal?
Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).
The constant \(\frac{\pi}{3}\) is, indeed, optimal.
Picture here.
Theorem 3 (Two Subsets of the Cirlce) For \(X,Y\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)\geq d_H(X,S^1)\).
Metric Graphs
Questions
Thank you
